Internet Archive's in-browser bookreader "theater" requires JavaScript to be enabled. It appears your browser does not have it turned on. Please see your browser settings for this feature.

A Simple Proof that Toffoli and Hadamard are Quantum Universal

by: Dorit Aharonov

Publication date: 2003-01-09

Collection: arxiv; additional_collections; journals

Language: English

Recently Shi proved that Toffoli and Hadamard are universal for quantum computation. This is perhaps the simplest universal set of gates that one can hope for, conceptually; It shows that one only needs to add the Hadamard gate to make a 'classical' set of gates quantum universal. In this note we give a few lines proof of this fact relying on Kitaev's universal set of gates, and discuss the meaning of the result.